package com.xk._02算法篇._04recrusion;

/**
 * @description: 汉诺塔
 * @author: xu
 * @date: 2022/10/15 22:23
 */
public class Hanoi {
    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        hanoi.hanoi(3, "A", "B", "C");
    }

    /**
     * 将 n 个碟子从 p1 挪动到 p3
     * 时间：O(2^n) 空间：O(n)
     * @param p2 中间的柱子
     */
    public void hanoi(int n, String p1, String p2, String p3){
        if (n == 1) {
            move(n, p1, p3);
            return;
        }
        hanoi(n-1, p1, p3, p2); // 将 n-1 个碟子从 p1 挪动到 p2
        move(n, p1, p3); // 将 最大的 那个碟子从 p1 挪动到 p3
        hanoi(n-1, p2, p1, p3); // 将 n-1 个碟子从 p2 挪动到 p3
    }
    /**
     * 将 no 号盘子从 from 移动到 to
     * @param no
     * @param from
     * @param to
     */
    private void move(int no, String from, String to) {
        System.out.println("将" + no + "号盘子从" + from + "移动到" + to);
    }
}
